/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2024-02-02
 * Time: 14:02
 *
 * https://www.nowcoder.com/share/jump/7745334641706853790784
 */
public class BM90 {

    // 检查是否是子串
    private boolean check(int[] hash) {
        for (int val : hash) {
            if (val < 0) {
                return false;
            }
        }
        return true;
    }

    public String minWindow(String S, String T) {
        // 滑动窗口
        // 使用数组作为 hash
        int[] hash = new int[128];
        // 初始化为负数
        for (int i = 0; i < T.length(); i++) {
            hash[T.charAt(i)]--;
        }
        // 双指针遍历
        int slow = 0, fast = 0;
        // 记录满足条件的字串边界范围
        int left = -1, right = -1;
        // 初始化最优解为整个 S 的长度
        int cnt = S.length();
        for (fast = 0; fast < S.length(); fast++) {
            char c = S.charAt(fast);
            // 哈希匹配
            hash[c]++;
            // 检查是否已经有满足条件的子串
            while (check(hash)) {
                // 满足条件开始取最优解
                if (cnt >= fast - slow + 1) {
                    // 更新最优解，记录最优解的位置
                    cnt = fast - slow + 1;
                    left = slow;
                    right = fast;
                }
                // 开始滑动
                c = S.charAt(slow);
                hash[c]--;
                slow++;
            }
        }
        // 没有子串
        if (left == -1) {
            return "";
        }
        // 有最优解
        return S.substring(left, right + 1);
    }
}
